Gate-level simulation is used extensively to verify the correctness of design netlists. Typically, input stimuli are applied to the netlist, and the simulation results are compared with a golden model or pre-defined checkers. When unknown values (Xs) exist, however, gate-level simulation can no longer produce correct results due to X-pessimism. Reference is now made to FIG. 1 showing a schematic diagram of an exemplary design netlist in which X-pessimism occurs. As FIG. 1 shows, the output of gate g4 should be 1 but logic simulation produces X instead. Such inaccuracy can produce numerous false Xs, rendering gate-level simulation useless. This problem is becoming severe due to physical optimizations and low-power requirements that allow Xs to exist in the design.
One simple prior art solution to the problem is to deposit random values at registers, such as the work by Hira et al., in U.S. Published Patent Application No. 2008/000950, entitled “Random Initialization of Latches in an Integrated Circuit Design for Simulation”. Such an approach eliminates X problems by converting the Xs into non-X values. However, each deposited value only represents one of the two possible values that the register can have. This can disadvantageously cause bugs to escape verification.
To properly fix gate-level simulation, the first step is to find false Xs produced during simulation. The earlier work of Chang et al., “Handling Nondeterminism in Logic Simulation So That Your Waveform Can Be Trusted Again”, IEEE D&T Early Access, 2011, proposed a formal technique and a methodology that can find false Xs generated during simulation. However, this solution to fix the problem is not generic. More specifically, this solution forces the correct values to the registers at the simulation time when the formal analysis was applied. This solution solves the problem at the particular time but does not resolve subsequent false Xs that may occur.
Oleg, in United States Published Patent Application No. 2010/0313175, entitled “Verification Systems and Methods”, proposed a technique to find X sources as well as the locations where such Xs can be trapped. However, he did not provide solutions on how to use the analysis to fix gate-level logic simulation for improved accuracy. In addition, his method analyzes all possible paths for X-propagation, requiring significant amounts of search space to be utilized.
Salz et al, in United States Published Patent Application No. 2012/0072876, entitled “Method and Apparatus for Reducing X-pessimism in Gate-level Simulation and Verification: proposed to resolve false Xs in gate-level simulation by duplicating a portion of the circuit (called a sub-circuit) and replacing Xs with 0 or 1 values to see if the output of the sub-circuit becomes 0 or 1. If so, the X is false. In their work, they required the user to indicate where X-pessimism may occur so that the analysis can be performed. However, identifying such logic is extremely difficult in practice. In addition, duplicating the sub-circuit to find false Xs is not only time-consuming but also requires a large mount of memory.
SimXACT Technique for Fixing X-Pessimism Issues
The prior U.S. Pat. No. 8,402,405 to Chang, et al, entitled SYSTEM AND METHOD FOR CORRECTING GATE-LEVEL SIMULATION ACCURACY WHEN UNKNOWNS EXIST, formally analyzes the trace to find fixes that can eliminate all combinational false Xs encountered during the simulation of the trace. The inputs to SimXACT are a trace as input stimuli, a gate-level netlist, and a start time that the Xs should be checked for the first time to determine whether they are false or not. The output is auxiliary code that when the same X-pessimism conditions are encountered, those false Xs will be replaced with the correct values.
SimXACT Works as Follows:
(1) At the start time, a check of the register data inputs is performed to check for Xs in the registers (typically denoted as “d”) to determine if they are false. The function used to check for Xs is shown below in table 1:
TABLE 1function checkX(input d, output subckt);1pi_frontier ← d; 2while (pi_frontier not empty)3 var ← pi_frontier.pop( );4 gate ← var.get_fanin_gate( );5 subckt ← subckt ∪ gate;6 foreach input ε gate.get_inputs( )7  if (input.value = x &&    input ∉ {design inputs,register outputs})8   pi_frontier ← pi_frontier ∪ input;9return proveX (subckt);
As shown, at line 1 of the illustrative code listing, the input d is inserted into pi_frontier, which is a set of inputs to the fan-in cone logic collected in subckt (the sub-circuit) thus far. The fan-in cone is then expanded by popping a variable, var, from pi_frontier (in line 3) and get the gate, gate, that fans out to the variable in line 4. The gate is then added to the sub-circuit, subckt, in line 5. In line 6, the inputs of gate are verified, or checked, and an input to pi_frontier is added if (1) the input has an X value in logic simulation, and (2) the input is not the primary input or a register output. The second condition stops fan-in extraction at register boundaries, rendering the analysis combinational. Line 9 calls the function proveX to prove whether the X in the sub-circuit's (subckt's) output, d, is real.
(2) For each false X, the fan-in cone of the register input is traced to find a portion of the cone, called a sub-circuit, whose inputs have real Xs and whose output is a false X. Algorithms ckt_minimize1, in table 2 below, and ckt_minimize2, in table 3 below, are used to achieve this goal.
TABLE 2function ckt_minimize1(input subckt.output subcktn); 1new_po ← subckt.get_output( ); 2subcktn ← subckt; 3do 4 gate ← new_po.get_fanin_gate( ); 5 c_po ← new_po; 6 foreach input ε gate.get_inputs( ) 7  subcktinput ← fanin cone of input in subckt; 8  if (input.value = x &&  proveX (subcktinput) = false) 9   new_po ← input;10   subcktn ← subcktinput;11 if (c_po = new_po)12  break;13return;
The function shown above in Table 2 initiates using the original output of the sub-circuit from the X checking process, checkX above, and traces the Xs in its fan-in cone until a real X is reached. The last false X then becomes the new output of the sub-circuit, subcktn, that also eliminates Xs. Note that during the tracing step, if there is more than one input that has a false X for a given gate, the illustrative procedure picks the first one (i.e. lines 6-8 of the code listing above). Accordingly, more than one iteration can be employed to eliminate all the false Xs, due to the X-eliminating sub-circuit now eliminating the X only at the chosen input. Accordingly, after a fix is found, the X in the fixed variable is replaced with its non-X value and logic simulation is performed on the original fan-in cone of the input d. Then d is verified to determine if it is X. If d is X, then the same repair analysis is performed again, and desirably repeats until d is no longer X. Thus, the false X at d is successfully and advantageously repaired by the fixes generated for its fan-in cone.
The code below in Table 3 is an example of a process for minimizing an X-elimination sub-circuit by moving its primary inputs towards its output. The input to the process is a sub-circuit, which is the sub-circuit (subcktn) returned by the first tracing process described above, for tracing the fan-in of false Xs to reduce the X-elimination sub-circuit from the output. The output of the second process for moving the input is a new sub-circuit saved as subcktn.
TABLE 3function ckt_minimize2(input subckt, output subcktn); 1subcktn ← subckt; 2do 3 changed= false; 4 foreach gate connected to subcktn.get_inputs( ); 5  subcktn ← subcktn \ gate; 6  if (proveX (subcktn) = false) 7   changed = true; 8   break; 9  else10   subcktn ← subcktn ∪ gate;11while (changed);12return;
In line 1 of the exemplary program code function/process, the sub-circuit, subckt, is copied to the new sub-circuit, subcktn. In lines 4-10 of the illustrative function, each gate that connects to the primary inputs of the new sub-circuit, subcktn, is removed to determine whether the output is still a false X. If the X is still false, the change is kept (lines 6-8). Otherwise, the gate is added back (line 10). This process repeats until no further gates can be removed (the do-while loop of lines 2-11 above). The inputs of the sub-circuit have now been moved as close to its output as possible.
(3) Generate false X elimination solution and auxiliary code based on the sub-circuit to eliminate such Xs.
(4) The generated fixes are applied by auto-fix to repair the current simulation values. Auto-monitor is then turned on to find further Xs that need to be checked throughout simulation.
After the analysis of the trace is finished, the generated auxiliary code can be used with future simulation to eliminate the false Xs. This flow allows gate-level simulation to produce correct results.
Auto-fix is used in the procedures to apply the generated fixes to repair simulation results instantly. Auto-fix works as follows: whenever a fix is generated dynamically during the SimXACT run, the procedure begins monitoring the simulation values of the fix conditions and deposits the non-X value to replace the false X on the target variable when the conditions match. When the values no longer match the conditions, the force is released. This can be implemented via the programming interfaces of modern simulators.
Auto-monitor examines simulation activities and applies X analysis to variables that can potentially have false Xs. More specifically, it monitors the gate-level simulation values on the fan-in cone of a register D input and checks for false Xs when the values in its fan-in cone change and the D input has an X value. In other words, a variable is checked again if the variable has an X value and the variables of its fan-in cone have value changes. This can also be implemented via the programming interfaces of modern simulators.
SimXACT analysis is comprehensive and is guaranteed to produce correct simulation results that match real hardware. However, sometimes the user only needs a small number of the generated fixes to make the test pass. In other words, many of the fixes, although effectively eliminating false Xs, are not needed as they do not affect test results.